package com.frx.leetcode.packageone;

/**
 * @author ：frx
 * @date ：Created in 2019/7/15 22:54
 * @description： 买卖股票的最佳时机，leetcode 121 题
 *              输入 [7,1,5,3,2,6]  输出 6 -1 = 5
 *              输入 [7,6,4,3,2,1]  输出 0
 * @modified By：
 * @version: ToDO
 */
public class BuyAndSellSock {

    public static void main(String[] args){
        int[] arr1 = {1,6,2,4,3,7};
        int[] arr2 = {7,6,4,3,2,1};
        long startTime = System.currentTimeMillis();
        int s1 = solution1(arr1);
        int s2 = solution1(arr2);
        System.out.println("cost : " + (System.currentTimeMillis() - startTime) + "ms");
        System.out.println(s1);
        System.out.println(s2);
        long startTime2 = System.currentTimeMillis();
        int s3 = solution2(arr1);
        int s4 = solution2(arr2);
        System.out.println("cost : " + (System.currentTimeMillis() - startTime) + "ms");
        System.out.println(s3);
        System.out.println(s4);

    }

    /** 解法一，暴力迭代*/
    public static int solution1(int[] arr){
        int maxPoint = 0;
        for (int i = 0; i < arr.length -1;i++){
            for (int j=i+1; j < arr.length;j++){
                int profit = arr[j] - arr[i];
                if (profit > maxPoint){
                    maxPoint = profit;
                }
            }
        }
        return maxPoint;
    }
    /** 解法二 峰和谷问题*/
    public static int solution2(int[] prices){
        int minPrice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i=0;i<prices.length;i++){
            if (prices[i] < minPrice){
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxprofit){
                maxprofit = prices[i] - minPrice;
            }
        }

        return maxprofit;
    }

}
